#define _CRT_SECURE_NO_WARNINGS 1

#include"QuickSort.h"

int GetMidi(int* a,int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] > a[midi])
	{
		if (a[midi] > a[right])//left midi right
		{
			return midi;
		}
		else if (a[right] > a[left])//right left midi
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else//left  <  midi
	{
		if (a[right] > a[midi])//right midi left
		{
			return midi;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

void PrintArray(int* a, int n)
{
	for (int i = 0;i < n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}

void Swap(int* a1,int* a2)
{
	int tmp = *a1;
	*a1 = *a2;
	*a2 = tmp;
}

void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return ;
	}
	int midi = GetMidi(a,left,right);
	Swap(&a[midi], &a[left]);
	int prev = left, cur = prev + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++; 
	}
	Swap(&a[keyi],&a[prev]);
	QuickSort(a,keyi,prev - 1);
	QuickSort(a,prev + 1,right);
}